<?php
/**
 * @title 面试题 08.03. 魔术索引 - 跳跃剪枝
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMagicIndex($nums) {
        /**
         * @since 2020-07-31 遍历
         */
        for ($i=0, $len=count($nums); $i<$len; ){
            if($i == $nums[$i]){
                return $i;
                break;
            } else {
                /**
                 * @since 2020-07-31 跳跃剪枝
                 */
                $i = max($i+1, $nums[$i]);
                // if($nums[$i] > $i){
                //     $i = $nums[$i];
                // } else {
                //     $i++;
                // }
            }
        }

        /**
         * @return
         */
        return -1;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.31_2.php
 */
$datas = [
    [0, 2, 3, 4, 5],
    [1, 4, 4, 4, 4],
    // [-531369933, -469065528, -430059048, -428981853, -319235969, -288076332, -286667432, -282312559, -197049680, -197022263, -174416117, -138027773, -121899023, -111631966, -107567458, -70437707, -52463072, -45519851, -38641451, -15825815, -3835472, -1525043, 22, 566842886, 593757472, 605439236, 619794079, 640069993, 657657758, 718772950, 815849552, 839357142, 936585256, 1006188278, 1042347147, 1057129320, 1062178586, 1069769438],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->findMagicIndex($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
